| 翻訳と辞書 |
| string graph ： ウィキペディア英語版 |
string graph
In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". Given a graph ''G'', ''G'' is a string graph if and only if there exists a set of curves, or strings, drawn in the plane such that no three strings intersect at a single point and such that the graph having a vertex for each curve and an edge for each intersecting pair of curves is isomorphic to ''G''.
== Background ==
described a concept similar to string graphs as they applied to genetic structures. In that context, he also posed the specific case of intersecting intervals on a line, namely the now classical family of interval graphs. Later, specified the same idea to electrical networks and printed circuits. The mathematical study of string graphs began with the paper and
through a collaboration between Sinden and Ronald Graham, where the characterization of string graphs eventually came to be posed as an open question at the 5th Hungarian Colloquium on Combinatorics in 1976.〔.〕 However, the recognition of string graphs was eventually proven to be NP-complete, implying that no simple characterization is likely to exist.〔 showed string graph recognition to be NP-hard, but was not able to show that it could be solved in NP. After intermediate results by and , completed the proof that the problem is NP-complete.〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「string graph」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|